package com.kehao.leetcode.algorithm;


import org.junit.Test;

import java.util.Collections;
import java.util.HashSet;

//https://leetcode-cn.com/problems/coin-change/
public class Solution322 {

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];  //dp[i]代表i元最少需要的硬币数量
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 9999999;
        }
        dp[0] =0;
        for (int i = 1; i < dp.length; i++) {
            boolean canPay = false;
            for (int coin:coins) {
                if(i-coin>=0){
                    if(dp[i-coin]!=-1){
                        dp[i] = dp[i]<dp[i-coin]+1 ? dp[i] : dp[i-coin]+1;
                        canPay = true;
                    }
                }
            }
            if(!canPay){
                dp[i] = -1;
            }
        }
        for (int i = 0; i < dp.length; i++) {
            System.out.print(dp[i]);
        }
        System.out.println();

        return dp[dp.length-1];
    }



    @Test
    public void myTest(){
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount));
    }

}
